1. Field of the Invention
Embodiments of the invention described herein pertain to the field of computer systems. More particularly, but not by way of limitation, one or more embodiments of the invention enable a system and method for ordering tasks with complex interrelationships.
2. Description of the Related Art
When altering the structure of a system, such as a database, care must be taken to ensure that the system retains its internal consistency and integrity at all times—even during the intermediary stages of the transformation. For example, during a transport operation (such as moving a database from a development to test environment or from a test environment to QA environment), there are several individual tasks that must be performed. Certain tasks must be scheduled execution before other tasks in order to achieve a valid result.
In classic task scheduling, a “dependency graph” may be created to identify and represent dependency relationships between tasks, and then a “topological sort” may be performed on the graph to attain an appropriate ordering of tasks with dependencies. (Information on dependency graphs and topological sort algorithms may be found at Wikipedia.com, among other sources, and are familiar to those of ordinary skill in the art of computer programming.) As with any dependency graph problem, circular dependencies must be excluded from any valid task ordering/scheduling.
As is understood by those of skill in the art, a process to order the tasks required to perform a transport operation, for example, would build a dependency graph of the tasks, and then perform a topologic sort on the tasks. The resultant ordered list of tasks may be executed to perform the transport operation while maintaining referential integrity of the database at all times. As long as the dependencies between the tasks are simple, such as “Task A must run before Task B,” then this approach works satisfactorily. However, this process cannot sufficiently represent all types of dependencies, such as where a task depends on the execution of more than two other tasks. For these complex dependencies, this approach fails.
Similar requirements may arise in other contexts, such as task scheduling by operating systems, route optimization for deliveries and related problems, organizational dynamics problems, and project planning programs for schedule development. These types of contexts, among others, require a method of ordering dependent tasks, among others.
For at least the limitations described above there is a need for a system and method for ordering tasks with complex interrelationships.